package leetcode;

/**
 * Created by baoyunfeng on 2019/8/1.
 * https://leetcode.com/problems/two-sum/description/
 * 思路：先排序从两边逐渐收缩先找到目标数字，再遍历原始数组得到目标数字的IndexN
 *      时间复杂度，插入排序算法N2，遍历数组N
 * 优化1：为nums数组直接建立相应index索引，索引根据数组的排序直接改变，找到目标数字时，索引即可得出。
 *       减少N数组遍历时间
 *       增加nums[]相应数量存储空间
 * 优化2：使用快排将空间复杂度将为nlogn
 *
 * 思路2 另外一种思路是固定一个数A，看SUM-A是否在这个数组之中。
 *       最坏其情况下最后两个比对的数才是目标数字，时间复杂度N2
 */
public class Two_sum_v2 {


    public static void main(String args[]) {
        int nums[] = {2, 5, 5,10};
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println(" ");
        int result[] = twoSum(nums, 10);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + " ");
        }
    }

    public static int[] twoSum(int nums[], int target) {
        int[] sortnums = nums.clone();
        insertSort(sortnums);
        int[] r = new int[2];
        int startIndex = 0;
        int endIndex = sortnums.length - 1;
        int start = 0;
        int end = 0;
        while (startIndex < endIndex) {
            int count = sortnums[startIndex] + sortnums[endIndex];
            if (count > target) {
                endIndex--;
            } else if (count < target) {
                startIndex++;
            } else {
                start = sortnums[startIndex];
                end = sortnums[endIndex];
                break;
            }
        }
        int rIndex = 0;
        for(int i = 0 ;i<nums.length;i++){
            if(nums[i]==start){
                r[rIndex] = i;
                rIndex ++ ;
            }else if(nums[i] == end){
                r[rIndex] = i;
                rIndex ++;
            }
        }
        return r;
    }

    //
    public static int[] insertSort(int nums[]) {
        if (nums == null && nums.length < 2) {
            return nums;
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j - 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = temp;
                }
            }
        }
        return nums;
    }
}
